from typing import List
class Solution:
    # 方法一：左右乘积列表
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # l和r分别表示左右两边的乘积
        l, r, answer = [0] * n, [0] * n, [0] * n
        # l[i]为索引i左侧所有元素的乘积
        # 对于索引为0 的元素，因为左侧没有元素，所以l[0]=1
        l[0] = 1

        for i in range(1, n):
            l[i] = nums[i - 1] * l[i - 1]
            print(l[i])
        print(l,"==")
        # r[i]为索引i右侧所有元素的乘积
        # 对于索引为n-1的元素，因为右侧没有元素，所以r[n-1]=1
        r[n - 1] = 1
        for i in reversed(range(n - 1)):
            r[i] = nums[i + 1] * r[i + 1]
            print(r[i])
        print(r,"==")
        for i in range(n):
            answer[i] = l[i] * r[i]
        print( answer,"==")
        return answer
    '''
    复杂度分析
    时间复杂度：O(N)，其中 N 指的是数组 nums 的大小。预处理 L 和 R 数组以及最后的遍历计算都是 O(N) 的时间复杂度。
    空间复杂度：O(N)，其中 N 指的是数组 nums 的大小。使用了 L 和 R 数组去构造答案，L 和 R 数组的长度为数组 nums 的大小。
    '''
    # 方法二：空间复杂度 O(1) 的方法
    def productExceptSelf2(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [0] * length
        answer[0] = 1
        for i in range(1, length):
            answer[i] = nums[i - 1] * answer[i - 1]

        r = 1
        for i in reversed(range(length)):
            answer[i] = answer[i] * r
            r *= nums[i]
        return answer
    '''
    复杂度分析
    时间复杂度：O(N)，其中 N 指的是数组 nums 的大小。分析与方法一相同。
    空间复杂度：O(1)，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。

    '''


# nums = [-1,1,0,-3,3]
nums = [1,2,3,4]
print(Solution().productExceptSelf(nums))

